506. Relative Ranks

#Algorithm #Algorithm-Heap_Sort #DataStructure-Heap #DataStructure-Priority_Queue

506. Relative Ranks

1. 문제

1-1. 원문

You are given an integer array score of size n, where score[i] is the score of the ith athlete in a competition. All the scores are guaranteed to be unique.

The athletes are placed based on their scores, where the 1st place athlete has the highest score, the 2nd place athlete has the 2nd highest score, and so on. The placement of each athlete determines their rank:

Return an array answer of size n where answer[i] is the rank of the ith athlete.

Example 1:
Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

Example 2:
Input: score = [10,3,8,9,4]
Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
Explanation: The placements are [1st, 5th, 3rd, 2nd, 4th].

Constraints:

1-2. 내용 번역

운동 선수별로 획득한 점수가 있다.
이 점수가 높은 순서대로 Gold Medal, Silver Medal, Bronze Medal을 받고 나머지 선수는 순위가 기록된다.
각 선수에 맞는 메달 혹은 순위를 기록한 배열을 리턴해라.

2. 문제 이해

2-1. 내용 이해

이 문제는 easy 난이도의 문제라 이해가 되지 않는 부분이 없을 문제이다.
힙과 우선순위 큐를 구현하고 사용해보고자 선택한 문제이다.

우선순위 큐를 구현하더라도 힙을 이용할 수 없는 경우가 있는데, 같은 우선순위가 있는 경우엔 힙을 구현할 수 없다. (힙의 가장 핵심 조건인 부모 노드의 값과 자식 노드의 값은 대소관계가 존재한다.는 조건을 위반할 가능성이 있기 때문이다.) 위의 경우는 모든 점수가 unique 하다는 조건을 더 추가해주었기 때문에 힙을 이용해서 우선순위 큐를 구현할 수 있었다.

2-2. 풀이 포인트

힙의 노드 위치를 정렬할 때의 기준이 노드의 값(운동선수의 인덱스)과는 다른 값(각 운동선수의 점수)을 기준으로 해야한다. 우선순위 큐를 사용한다고 할 수 있는 이유이다. 이 부분에 유의해서 힙을 구현하고 힙정렬을 해보자.

3. 구현

class Solution {
    fun findRelativeRanks(score: IntArray): Array<String> {
        val heap = createHeap(score)

        val heapSortedIdxs = heapSort(heap, score)
        val resultArr = Array<String>(heapSortedIdxs.size){""}

        for(i in 0..heapSortedIdxs.size-1) {
            resultArr[heapSortedIdxs[i]] = when(i) {
                0 -> "Gold Medal"
                1 -> "Silver Medal"
                2 -> "Bronze Medal"
                else -> "${i+1}"
            }
        }

        return resultArr
    }

	/* minHeap으로 생성하고 delete할 때 끝에부터 넣는 방식으로 오름차순을 구현한다. */
    // minHeap
    fun createHeap(score: IntArray): ArrayList<Int> { 
        val pq: ArrayList<Int> = arrayListOf()

        for(i in 0..score.size-1) {
            pq.add(i)

            var idx = pq.size-1

            while(idx > 0) {
                val parentIdx = (idx+1)/2-1

				// (핵심!!) 노드의 대소 관계를 노드안의 값이 아닌 운동선수의 점수로 비교한다.
                if (score[pq[parentIdx]] > score[pq[idx]]) {
                    val temp = pq[parentIdx]
                    pq[parentIdx] = pq[idx]
                    pq[idx] = temp

                    idx = parentIdx
                } else {
                    break
                }
            }
        }

        return pq
    }

	/* 힙 소트를 하고 난 결과는 노드의 값에 따라서가 아닌 점수에 따라서 정렬 된다. 
	 * 정렬은 점수에 따라서 되지만 정렬되는 값은 운동선수의 인덱스 번호이다.
	 */
    fun heapSort(list: ArrayList<Int>, score: IntArray): Array<Int> {
        val sortedArray: Array<Int> = Array(list.size){0}

        while(list.size > 0) {
            val pulledItem = pullFromHeap(list, score)
            sortedArray[list.size] = pulledItem
        }

        return sortedArray
    }

	/* 최소의 점수를 가진 운동선수의 번호를 리턴한다. */
    fun pullFromHeap(list: ArrayList<Int>,score: IntArray): Int {
        val pullItem = list[0]
        list[0] = list[list.size-1]
        list.removeAt(list.size-1)

        var idx = 0
        while((idx*2+1) < list.size) {
            val leftChildIdx = idx*2+1
            val rightChildIdx = leftChildIdx+1

            var compareIdx = leftChildIdx

			// (핵심!!) 노드의 대소 관계를 노드안의 값이 아닌 운동선수의 점수로 비교한다.
            if(rightChildIdx < list.size && score[list[compareIdx]] > score[list[rightChildIdx]]) {
                compareIdx = rightChildIdx
            }

			// (핵심!!) 노드의 대소 관계를 노드안의 값이 아닌 운동선수의 점수로 비교한다.
            if (score[list[idx]] > score[list[compareIdx]]) {
                val temp = list[compareIdx]
                list[compareIdx] = list[idx]
                list[idx] = temp

                idx = compareIdx
            } else {
                break
            }
        }

        return pullItem
    }
}